package com.example.heuristicallysearchalgorithm49;

/**
 * 可以修改的优先队列(构建小顶堆)
 * @auther lijiewei
 * @date 2022/9/26 16:37
 */
public class PriorityQueue {

    //数组，从下标1开始存储数据
    //数组中下标为i节点的左子节点下标为i*2
    private Node[] nodes;
    //堆可以存储的最大数据个数
    private int n;
    //堆中已经存储的数据个数
    private int count;

    public PriorityQueue (int vcapacity) {
        this.nodes = new Node[vcapacity+1];
        this.n = vcapacity;
        this.count = 0;
    }

    /**
     * 获取队列头节点，并删除它（为空，返回null）
     * @return
     * @author lijiewei
     * @date   2022/9/26 16:55
     */
    public Node poll() {
        if (this.isEmpty()) {
            return null;
        }
        Node temp = nodes[1];
        nodes[1] = nodes[count];
        nodes[count] = null;
        count--;
        //自上往下堆化
        heapify(1, count);
        return temp;
    }

    /**
     * 添加一个元素（已满，抛异常）
     * @param node
     * @return
     * @author lijiewei
     * @date   2022/9/26 20:18
     */
    public void add(Node node) {
        if (count >= n) {
            throw new RuntimeException("队列已满");
        }
        count++;
        nodes[count] = node;
        int i = count;
        //自下往上堆化
        while (i/2 > 0 && nodes[i].getF() < nodes[i/2].getF()) {
            swap(i, i/2);
            i = i/2;
        }
    }

    /**
     * 更新元素
     * @param node
     * @return
     * @author lijiewei
     * @date   2022/9/26 20:30
     */
    public void update(Node node) {
        int id = node.getId();
        //数组，从下标1开始存储数据
        for (int i = 1; i < nodes.length; i++) {
            if (nodes[i].getId() == id) {
                nodes[i].setDist(node.getDist());
                nodes[i].setF(node.getF());
                break;
            }
        }
        //重新堆化，从最后一个非叶子节点开始
        for (int i = count/2; i > 0; i--) {
            heapify(i, count);
        }
    }

    /**
     * 至上往下堆化
     * @param i 开始下标
     * @param n 尾下标
     * @return
     * @author lijiewei
     * @date   2022/9/26 17:08
     */
    private void heapify(int i, int n) {
        while (true) {
            int minPos = i;
            if (i*2 < n && nodes[i].getF() > nodes[i*2].getF()) {
                minPos = i*2;
            }
            if (i*2+1 <= n && nodes[minPos].getF() > nodes[i*2+1].getF()) {
                minPos = i*2+1;
            }
            if (minPos == i) {
                break;
            }
            swap(i, minPos);
            i = minPos;
        }
    }


    /**
     * 交换下标为 i 和 j的两个元素
     * @return
     * @author lijiewei
     * @date   2022/9/26 20:16
     */
    private void swap(int i, int j) {
        Node temp = nodes[i];
        nodes[i] = nodes[j];
        nodes[j] = temp;
    }


    /**
     * 判断是否为空
     * @return
     * @author lijiewei
     * @date   2022/9/26 16:59
     */
    public boolean isEmpty() {
        return count <= 0;
    }

    /**
     * 清空
     * @return
     * @author lijiewei
     * @date   2022/9/26 16:59
     */
    public void clear() {
        this.nodes = null;
        this.n = 0;
        this.count = 0;
    }
}
